插入排序是一種簡單直觀是用少量元素的排序

白話說插入排序將列表分成已排序和未排序兩部分，一開始已排序部分只包含第一個元素，而未排序部分包含其餘元素，逐一取出未排序部分的元素，並將它插入到已排序部分的正確位置，以確保已排序部分仍然保持有序～

當數據超大時雖比其他複雜度較低但需要更多記憶體的排序算法執行得更快

• 最佳情況O(n)/最壞情況O(n^2)完全倒序/平均情況O(n^2)時間複雜度
• 穩定排序（相同元素的相對位置每次排序完全一致）

假設我們有一個列表 [12, 11, 13, 5, 6]，我們將按照升序（由小到大）進行排序
開始時，已排序部分只包含第一個元素 12，未排序部分包含其餘元素 [11, 13, 5, 6]
Step1：取出未排序部分第一個元素11，將其插入到已排序部分的正確位置，在這種情況下，它留在原地，因為 11 比 12 小
=> 過程：已排序部分 [11, 12]，未排序部分 [13, 5, 6]
Step2：接著取出未排序部分的下一個元素 13，每一步遍歷比較將它插入到已排序部分的正確位置。在這種情況下，它放在最右邊，因為它比已排序部分中的所有元素都大
=> 過程：已排序部分 [11, 12, 13]，未排序部分 [5, 6]
重複以上步驟直到所有元素都被插入到已排序部分
最終，列表 [11, 12, 13, 5, 6] 將被排序成 [5, 6, 11, 12, 13]

def insertion_sort(arr):
    # Step1：取出未排序部分第一個元素將其插入到已排序部分的正確位置
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Step2：接著取出未排序部分的下一個元素，每一步遍歷比較將它插入到已排序部分的正確位置
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key


my_list = [12, 11, 13, 5, 6]
insertion_sort(my_list)
print("排序後的列表:", my_list)